package algo;

import model.tsp.Problem;
import model.tsp.Solution;
import util.CheckUtils;
import util.PrinterUtils;

import java.util.List;
import java.util.TreeSet;

import static algo.Operator.*;
import static util.RandomUtils.randomNPoints;

public class LocalSearch extends HeuristicSearch {


    public LocalSearch(Problem problem) {
        super(problem);
    }

    public void solve() {
        Solution initSolution = initial();
        PrinterUtils.printTspResult("local search init", initSolution);
        Solution finalSolution = improve(initSolution);
        PrinterUtils.printTspResult("local search final", finalSolution);
        //CheckUtils.check(finalSolution, distance);
        //plot(finalSolution);
    }

    protected Solution initial() {
        GreedySearch greedySearch = new GreedySearch(problem);
        return greedySearch.search();
    }

    protected Solution improve(Solution initSolution) {
        return localSearch(initSolution);
    }

    protected Solution localSearch(Solution solution) {
        int k = 1;
        int kMax = 6;
        int localSearchCnt = 3000;
        while (k <= kMax) {
            Solution localBestSolution = solution.copy();
            // 局部搜索过程，搜索邻域k中的较优解
            for (int i = 0; i < localSearchCnt; i++) {
                List<Integer> newX = null;
                if (k == 1) {
                    newX = neighborhoodOperator1(solution.getPermutation());
                } else if (k == 2) {
                    newX = neighborhoodOperator2(solution.getPermutation());
                } else if (k == 3) {
                    newX = neighborhoodOperator3(solution.getPermutation());
                } else if (k == 4){
                    newX = neighborhoodOperator4(solution.getPermutation());
                } else if (k == 5) {
                    newX = neighborhoodOperator5(solution.getPermutation());
                } else if (k == 6){
                    newX = neighborhoodOperator6(solution.getPermutation());
                } else {
                    throw new RuntimeException("超出neighborhood邻域集合长度: " + k);
                }
                int fitness = calculateFitness(newX);
                if (fitness < localBestSolution.getCost()) {
                    localBestSolution = new Solution(newX, fitness);
                }
            }
            // 邻域切换过程
            if (localBestSolution.getCost() < solution.getCost()) {
                solution = localBestSolution;
                k = 1;
            } else {
                k++;
            }
        }
        return solution;
    }

    //*********************  操作算子随机变换 **************************************/

    protected List<Integer> neighborhoodOperator1(List<Integer> permutation) {
        TreeSet<Integer> points = randomNPoints(2, permutation.size(), random);
        int first = points.first();
        int second = points.last();
        return relocatedOperator(permutation, first, second);
    }

    protected List<Integer> neighborhoodOperator2(List<Integer> permutation) {
        TreeSet<Integer> points = randomNPoints(2, permutation.size(), random);
        int first = points.first();
        int second = points.last();
        return twoOptOperator(permutation, first, second);
    }

    protected List<Integer> neighborhoodOperator3(List<Integer> permutation) {
        TreeSet<Integer> points = randomNPoints(2, permutation.size(), random);
        int first = points.first();
        int second = points.last();
        return exchangeOperator(permutation, first, second);
    }

    protected List<Integer> neighborhoodOperator4(List<Integer> permutation) {
        TreeSet<Integer> points = randomNPoints(2, permutation.size(), random);
        int first = points.first();
        int second = points.last();
        return rightShiftOperator(permutation, first, second,1);
    }

    protected List<Integer> neighborhoodOperator5(List<Integer> permutation) {
        TreeSet<Integer> points = randomNPoints(2, permutation.size(), random);
        int first = points.first();
        int second = points.last();
        return leftShiftOperator(permutation, first, second,1);
    }

    protected List<Integer> neighborhoodOperator6(List<Integer> permutation) {
        TreeSet<Integer> points = randomNPoints(2, permutation.size(), random);
        int first = points.first();
        int second = points.last();
        return orOptOperator(permutation, first, second);
    }


}
